
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半
    priority_queue<int, vector<int>, less<int>> B; // 大顶堆，保存较小的一半
    MedianFinder() { }
    void addNum(int num) {
        if(A.size() != B.size()) {
            A.push(num);
            B.push(A.top());//取了A中最小的放到B中
            A.pop();//删除A中最小的
        } else {
            B.push(num);
            A.push(B.top());//取了B中最大的放到A中
            B.pop();
        }
    }
    double findMedian() {
        return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;//设计的就是A中元素(个数)>=B中元素(个数),所以一旦size不相等就先往A中添加元素
    }
};
int main(int argc,char const *argv[]){
    MedianFinder mf;
    mf.addNum(1);
    mf.addNum(3);
    mf.addNum(2);
    mf.addNum(4);
    mf.addNum(5);
    printf("%.2f ",mf.findMedian());
    return 0;
}